package bitalgorithm

/*应用1： 快速取模*/
func QuickExponentMode(a int64, e int64, m int64) int64 {

	var a_current int64

	var result int64 = 1
	var a_next = a % m

	for {
		if e != 0 {
			if e&1 != 0 {
				a_current = a_next
				result = (result * a_current) % m
			}
		} else {
			break
		}

		e >>= 1
		a_next = (a_current * a_current) % m

	}
	return result

}

/*应用2： 求取所有的1的个数*/

/*
k = k&(k-1)可以消除k的二进制数的最后一个1.(从大到小)
连续进行这个操作，每次消除一个1，直到全部消除为止。
操作次数就是1的个数。
*/
func CalcOneBitInANumber1(number int64) int64 {
	var count int64 = 0
	var num = number
	for num != 0 {
		count += 1
		num = num & (num - 1)
	}
	return count
}

/*
k=k&(k-1)可以消除k的二进制数的最后一个1.
连续进行这个操作，每次消除一个1，直到全部消除为止。
操作次数就是1的个数。

递归公式形式: (将n计算问题转化为 <n计算问题 从小到大)
onebitCount[k] = onebitCount[k&(k-1)] + 1
*/
func CalcOneBitInASetOfNumber(number int64) []int64 {
	var idx int64 = 0
	var bitCountList []int64 = make([]int64, number)
	bitCountList[0] = 0
	for idx = 1; idx < number; idx++ {
		bitCountList[idx] = bitCountList[idx&(idx-1)] + 1
	}
	return bitCountList
}

/*
递归公式形式: (将n计算问题转化为 <n计算问题 )
需要将n之前的所有数都算过了才能够得知n问题的答案
if number is odd number ,
  onebitCount[n] = onebitCount[n-1] + 1
if number is even number,
  onebitCount[n] = onebitCount[n>>1]
*/
func CalcOneBitInASetOfNumber2(number int64) []int64 {
	var idx int64 = 0
	var bitCountList []int64 = make([]int64, number)
	bitCountList[0] = 0
	for idx = 1; idx < number; idx++ {
		if idx&1 == 1 {
			bitCountList[1] = bitCountList[idx-1] + 1
		} else {
			bitCountList[1] = bitCountList[idx>>1] + 1
		}
	}
	return bitCountList
}

func CalcOneBitInANumber2(number int64) int64 {
	var count int64 = 0
	var num = number
	for (num>>1)&1 == 1 {
		count += 1
		num = num & (num - 1)
	}
	return count
}

/*
异或定理：自己异或自己为0， 0 异或自己为自己
推理：奇数个自己的异或为自己，偶数个自己的异或为0

应用1：
求取所有数中只出现奇数次的一个数
*/
func FindOddNumber(numberList []int64) int64 {
	var result int64
	for i := 0; i < len(numberList); i++ {
		if i == 0 {
			result = numberList[i]
		} else {
			result ^= numberList[i]
		}
	}
	return result
}

/*
推理：奇数个自己的异或为自己，偶数个自己的异或为0
应用2：
不引入新的变量进行数的交换*/

func Swap(x int64, y int64) {
	x ^= y
	y ^= x
	x ^= y
}

/*
异或原理：只有不同的值，异或以后才会是1
应用1：求两个数中值不同的位数的个数
*/
func CountDifferentBit(x int64, y int64) int64 {
	var count int64 = 0
	for xor := x ^ y; xor > 0; xor = xor & (xor - 1) {
		count += 1
	}
	return count
}

/*
计算两个数均值 保证不溢出
1、x&y 表示什么？

     它取出了两个数中均为1的bit位x1和y1，同时它也等于(x1+y1)/2的值，为什么呢？很简单，因为1+1的均值就是1，恰巧等于&运算的结果。例如，（0010 + 0010）/2 = 0010;  这样我们就通过x&y运算求得了最终均值的第一部分；

2、(x^y)>>1表示什么？

    右移一位表示除以2这个大家都很清楚，而x^y则表示两个数中bit位一个为0一个为1的位，而巧妙的是，0+1=1正好是异或运算的结果。所以(x^y)>>1就表示了均值的剩下那一部分；



3、为什么可以将均值分成这样的两个部分？

    我想这是理解原理的关键，也是理解二进制的关键。

    我们知道十进制的加法里，比如,302+210，其实本质上它应该写成这样，3*100+0*10+2 和 2*100+1*10，也就是说，对应10的幂的系数不为0，那么这些系数对应的项将对求和结果作出”贡献“；同理，二进制的加法里，假设 100011 + 101101，可以按”贡献“对bit位进行分类，全为1，全为0，有一个1的三种。其中全为0的位对求和没有任何”贡献“，所以我们不予考虑。那么现在就考察两种，全为1和有一个1的bit，我们不妨将原数字写成两个部分,：

100011 = 100001 + 000010，

101101 = 100001 + 001100，



这样我们就将原数分解为两部分，两数均为1的bit位和只有一个1的bit位。对这两部分分别求均值。

100001+100001的均值显然仍为100001，这就是x&y的结果；

000010+001100的均值即(x^y)>>1；

最后将两部分相加即原数的均值；



最后一个问题，为什么这样计算就不会溢出？

会不会溢出主要看+运算，也就是看x&y和(x^y)>>1这两个数的最高位是否有可能都为1，如果有可能，那么就可能溢出，反之亦然。
如果x&y的最高位为1，那么x和y的最高位均为1，那么x^y的最高位肯定是0，根据计算机右移操作补最高的原则，(x^y)>>1的最高位同样也为0，所以两部分相加一定是1+0，不会出现溢出。那么有人会说，第二位如果有进位呢？



我们可以看出，x&y和x^y这两个结果中，所有的bit位都是相反的，即如 101010 和 010101 这样的结果，把后者右移一位，会出现进位到最高位的情况吗？

出现进位的bit一定是后者的1右移一位正好遇到前者的1，那么这时候后者这个1前面的第一个0右移之后一定会遇到前者的0，这样就不会导致进位到最高位的情况。除非后者全为1，如果全为1，那么前者一定全为0，显然相加不会出现溢出。

所以这样的位运算不会产生溢出。
————————————————
版权声明：本文为CSDN博主「wyzsdx」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wyzsdx/article/details/46669369
*/

func Average(x int64, y int64) int64 {
	return (x&y + (x^y)>>1)
}
